The present invention relates, in general, to a device-independent, frequency-driven layout system and method for field programmable gate arrays ("FPGA"). More particularly, the present invention allows an FPGA circuit designer to specify the desired operating frequencies of clock signals in the FPGA design to the frequency-driven layout system of the present invention which will then, if possible, generate a physical layout for the device that will allow it to operate at the specified frequencies. Actual net, path and skew requirements are automatically generated and fed to the place and route tools. This is effectuated by evaluating the frequency constraints, determining what delay ranges are acceptable for each electrical connection and targeting those ranges throughout the layout synthesis.
Field programmable gate arrays ("FPGA") are a relatively new technology, first introduced by Xilinx, Inc. in 1985. An FPGA consists of cells which can be programmed to perform a variety of logical functions and programmable interconnects to connect the logic cells in a general way. The cells and interconnects are used to implement complex logical circuits. The use of FPGA's continues to grow at a rapid rate due to their relatively shorter design cycles, reduced cost through logic consolidation and the flexibility offered by their re-programmability. With an FPGA's inherent flexibility also comes additional timing problems not encountered, for example, in the use of gate arrays due to the fact that an FPGA uses programmable switches having inherently less predictable and greater delay characteristics, fixed interconnect resources and logic cells which are generally coarser than other types of programmable devices.
However, despite the advantages offered by FPGA's, one of the significant shortcomings of the devices is their limited speed. Utilizing the automatic map place and route tools provided by the FPGA manufacturers themselves, designs implemented in today's technology typically can achieve maximum operating frequencies of only about 30 to 40 Mhz. Nevertheless, even though the devices continue to attain faster operating speeds due to improved process technology, many of today's board level designs require operating frequencies in the 50 to 100 Mhz range. Moreover, competing technologies such as programmable logic devices ("PLD") and gate arrays are likewise becoming faster.
Previously, designers have attempted to maximize chip performance by becoming so knowledgeable in a particular device's architecture and proficient at designing in that particular device, that through meticulous design capture and manual place and route, the designers were able to do a more effective job of programming than with the use of the automatic tools provided by the FPGA manufacturer. Nevertheless, as such devices become larger and inherently more complex, it is increasingly more difficult to do the design manually. Moreover, with the introduction of additional FPGA's from still other manufacturers, whole new architectures are presented, each with its own unique strengths and weaknesses. It is, therefore, becoming increasingly difficult for a designer to become expert in working with each of the many different available designs.
Typically, the process for implementing a design in an FPGA begins with the device selection. In this regard, the designer typically attempts to maximize the efficiency of his implementation by careful selection of the device, given its inherent limited size and speed. The second primary step is termed "design capture" and the vast majority of FPGA designs are "captured" utilizing schematics. Alternative design capture techniques include programmable array logic/programmable logic device ("PAL/PLD") behavioral languages such as Abel and Palasm and hardware description languages such as VHDL and Verilog. Functional simulation follows design capture. However, simulation of the actual timing cannot be done because the design exists only in terms of a logical representation and there is no physical information available on which to base the functional simulation.
The next step in the design process is the mapping of the design into the target device. Mapping, or "fitting" is that stage of the design in which the logical information is converted into the technology-specific components unique to the physical device targeted for implementation; that is, the logic blocks within a particular FPGA. Some device specific optimization can occur at this point and some designers wait until after mapping to do the above-described functional simulation thereby allowing them to do some preliminary timing simulation at the same time, even though, until place and route is complete, the only timing information available are the component delays.
Once the design has been converted into the logic blocks available within the specific targeted device, they must be placed and routed. This is typically a lengthy phase of the design process and, unlike gate arrays, FPGA's are fixed in size and if the design does not automatically place and route to completion, getting it to fit within the targeted device can prove to be very difficult. It is also important to understand that even a completely routed design can still be a long way from a working design. Getting the timing inside the targeted device to work properly, and at the desired operating frequency, is typically the most time consuming, and error prone, part of the design process.
Current design techniques include following the routing of all the connections with timing analysis or timing simulation (or a combination of both techniques) in order to find the problems that would keep the device from running at the desired operating frequency. This is an iterative process as the designer runs timing analysis (or simulation), finds and fixes a problem, runs timing analysis again to find the next problem and so on, until the design works. Other techniques which designers may implement include using static random access memory ("SRAM") based devices to build a prototype board to aid in identifying timing problems and then fixing them at lower operating speeds, raising the speed a notch, finding and fixing new problems and so on, until the desired operating frequency is obtained.
The inherent flexibility of FPGA's makes them more susceptible to timing problems than other technologies such as PAL's, PLD's, gate arrays and standard cells. For example, because of the more varied logic blocks used in FPGA's, (as compared to the relatively fine-grain elements utilized in gate arrays), without good device-specific optimization, logic functions may not be efficiently implemented to the particular architecture being used thereby resulting in extra delays through potentially critical paths. This problem is especially acute with relatively coarse-grain architectures such as AT&T's ORCA and Xilinx's 3,000/4000 Series devices. The number of permutations of logic elements within these devices is so great that current synthesis tools simply do not work, and in general, special mapping algorithms must be developed.
Another difficulty encountered in the programming of FPGA's is that the average interconnect delays within the typical device are greater than those on an associated printed circuit board ("PCB") or gate array, making it difficult to obtain perfectly synchronized timing while at the same time creating a higher penalty for poorly routed connections. The heterogeneous interconnect resources of the aforedescribed Xilinx devices, or the ability to route through logic blocks and architectures such as is found in Pilkington and Concurrent devices further complicates the situation. These unique FPGA characteristics make it particularly difficult to get all devices timing optimized, as the delay on any particular path can change significantly depending on which route is taken. This commonly results in skew and setup-and-hold violations.
Another problem encountered in programming FPGA's is that there may simply not be sufficient routing resources of the proper type to readily implement the design. Problems may be encountered in finding adequate routing resources such as dedicated clock lines or interconnects which can handle wide fanout circuitry with minimal delay variances. As has been previously described, interconnect resources within FPGA's are both fixed and relatively limited. In fact, the larger devices currently available are even more susceptible to these type of problems due to the increased demand placed upon them for global interconnect resources.
Further, the limited operating speeds of current FPGA's provide additional constraints forcing programmers to find alternative techniques for optimizing the devices for their maximum operating frequencies. As has been described, obtaining the maximum operating speed of a particular device is important, while at the same time, FPGA's are particularly susceptible to timing problems which affect the ability to obtain this desired performance. While the most important single step in implementing an FPGA design is choosing the proper device based upon its size, speed and architecture, most of the time spent in designing a working device is spent in getting the device timing to work.
Therefore, it can been seen that there are two primary ways to shorten FPGA design cycles. That is, one can either shorten the time it takes to get through the process of mapping, optimization, placement, routing, timing analysis and programming and/or reduce the number of times that one needs to go through that process to get working results. Typically, the design flow of a FPGA device comprises an iterative process of laying out the design, checking the timing using timing analysis and/or timing simulation, making changes to the layout and then rechecking the timing. Inherent in this iterative process is that changing the layout in one part of an FPGA in an attempt to fix a particular timing problem can easily cause a concomitant timing problem to appear somewhere else in the design.
Therefore, an optimal solution to these problems is the ability to set timing requirements up front and then have the design tools automatically meet them during, implementation. Such a "timing-driven" approach shortens the design cycle by eliminating the need to run multiple iterations of place and route, or having to resort to manual "tweaking" of the design in an attempt to repair timing problems and maximize operating frequency. Moreover, having the ability to set timing requirements up front allows all critical nets of the device to be constrained by these timing requirements and, therefore, changes can be made to the design without causing concomitant timing problems elsewhere in the device. The ability to deal with timing issues dynamically, during placement and routing, allows the designer to shorten design cycles significantly.
In order for the design process of a FPGA to be truly timing-driven, two criteria must be met5 First, the designer has to be able to specify the exact timing requirements up front, before the automatic design tools are engaged. Next, the automatic tools (mapping/placement/routing) have to be designed to complete their task while simultaneously adhering to the timing rules as input by the designer. Therefore, timing requirements, such as clock frequency, offset (the off-chip timing relationships between clock and data signals), and external setup/hold times should be considered along with physical constraints like package type and pinout assignments early in the design process. Because most of the timing requirements will be in terms of the logical design, such need first be converted into constraints that the physical implementation tools can relate to, such as specific paths, nets and maximum skew, before being handed off to the mapping, placement and routing routines. In general, FPGA programming can be broken down into four steps comprising technology mapping/optimization, placement, routing and programming.
With regard to the mapping/optimization step of FPGA programming, there are at least three different approaches. First, the optimization algorithms may be "fixed" and make pre-set tradeoffs between device area and speed. (Typically, optimizing for speed entails "flattening" the hierarchy of the circuitry, but this usually results in the circuitry taking up more space or area). Alternatively, the designer may be provided with control over whether the mapper optimizes more for area or more for speed. Finally, the mapper may be truly "timing-driven" although typically the only timing evaluation which may take place is component delays, since when there is no placement and routing information from which to determine interconnect delays, such cannot be considered.
The second step of FPGA programming is placement, and while speed enhancing mapping algorithms can provide incremental improvements over a solution which only provides timing-driven placement and timing-driven routing, a timing-driven mapping capability without timing-driven place and route will prove insufficient. Currently, the state of the art in FPGA design tools has relied on a process called "delay-based cleanup" to reduce overall interconnect delays. With delay-based cleanup, the designer is only allowed to enter net/signal priorities (that is, signal A has a higher priority than signal B). Such tools provide no capability to enter specific, detailed timing requirements and thus, such tools cannot possibly meet timing requirements because they have never been specified. Basically, a cleanup pass is run after the design has been routed to 100% completion with the tools attempting to reduce the average delay of all nets in the design. Among the disadvantages of such delay-based cleanup techniques is that the tools do the same thing each time, and as an example, high priority nets are always routed first, regardless of the results. Further, the tools don't necessarily balance the use of available resources, and some nets may be "faster" than they need to be only because they were routed first and, therefore, use up valuable routing resources that were not really needed, while others may not be fast enough. Finally, not enough information is provided for the tools to act intelligently, and there is no way for them to report back whether they have balanced the use of available resources or where potential problems may exist.
Utilizing truly timing-driven techniques, the designer may specify exact timing constraints for all paths, nets, skew and so forth (as an example, all points on signal A must be under 15 nanoseconds, and the clock skew for net X must be under 3 nanoseconds). Among the many advantages to utilizing a truly timing-driven technique is that the tools would then have the necessary information with which to attempt to balance the use of available resources and allow them to work on the problems until all input requirements are met. Further, potential timing problems are, therefore, addressed up front, as opposed to the numerous iterations required to find and fix problems after layout of the FPGA is complete. This significantly shortens the design cycle and aids in eliminating the possibility of creating a new problem somewhere else on the device while attempting to fix an existing one. Moreover, when properly implemented, true timing-driven capability would preclude the unnecessary ripping up of acceptably placed and routed circuitry as changes are made to the design, thereby also shortening the design cycle. While there are numerous advantages to timing-driven approaches, it is nevertheless incumbent upon the designer to know, up front, his exact timing requirements and to assign them specifically and correctly to the appropriate paths and nets. Depending on the design and size of the device, this could include anywhere from several dozen to several hundred signals.
Therefore, it would be highly desirable to provide an FPGA designer with the benefits of true timing-driven techniques while allowing him to specify his requirements in high-level terms such as frequency and offset. Such would then result in a "frequency-driven" design technique where actual net, path and skew requirements would then be automatically generated and passed to the place and route tools. Therefore, a frequency-driven design approach would provide all of the same benefits as a timing-driven approach, but would allow the input of merely a single preference (such as clock frequency) and the system would automatically generate and assign constraints to the literally thousands of signals on the device automatically, relieving the designer of the difficult task of manually identifying the paths and signals and the exact timing requirements himself. Moreover, since all potentially critical paths in the device are then automatically assigned constraints, the tools have the requisite information to analyze and optimize the design for best results. Balancing timing between multiple different paths at the same time requires the manipulation of large amounts of data while simultaneously solving equations.
In order to effectuate such a "frequency-driven" design, timing analysis must be integrated into the total timing/frequency-driven solution such that analysis can be run using the designer's original input constraints/preferences as the measurement criteria. Such timing analysis functionality, when combined with the detailed and accurate set of timing constraints needed to achieve a desired operating frequency, allows for a technique which can pinpoint exactly where an implemented design has failed to meet the designers specified timing requirements as well eliminating the problems inherent in the conventional approach of manually sorting through vast amounts of data to pinpoint such problems.